Dynamic collections are data elements for computer programming that can have a variable number of elements at run time. Although dynamic collections are widely used, they presently give rise to significant programming complexity. The reasons for this can be better appreciated in connection with a brief description of implementing dynamic collections in an object-oriented setting. Typically, such an implementation includes a set of interface procedures that manipulate the underlying data structure(s) selected to implement the collection. The interface procedures are usually the only way to access or change the underlying data of the collection, so the set of interface procedures is typically referred to as “the interface” for the collection. The collection may be part of an application defined type (ADT), and in such cases, operations on instances of the ADT rely on the collection interface provided as part of the ADT interface.
Manual coding of the interface for a collection is relatively difficult and error-prone programming. Implementation of simple operations on a collection frequently requires complex interface code to express top-level collection operations in terms of individual actions on a complex underlying data structure. Another difficulty is that it is easy to introduce subtle errors into a program by omitting consideration of all possible states a collection can be in. For example, if collection B is intended to be a clone of collection A, it is easy to see that additions and deletions relating to A should also be done for B. However, this is not sufficient to make B a clone of A. It is also necessary to ensure that when B is created, all possible states of A are provided for in the code to initialize B. Further complications may arise if B is created before A. The complexity inherent in providing such interfaces is presently one of the factors driving further evolution of programming languages. For example, the collection templates provided by the C++ standard template library use essentially every feature of the C++ language, and the languages Java and C# have recently been extended to provide support for generics to facilitate implementation of collections.
In some situations, the complexity of dealing with dynamic collections can be reduced with conventional methods. For example, some languages provide for data types which are dynamic collections (e.g., lists, variable length arrays, etc). In such cases, operations involving these data types can be coded more simply by a programmer than in the above approach. For example, if A and B are variable length arrays of floats provided as a language type, then the program statement A+B can cause the translator to automatically generate code to perform the implied element-by-element additions over the appropriate range of array indices. This substantially reduces the burden on the programmer.
However, such type-based collections are not a complete solution to the above-described difficulties. The main reason for this is that a considerable degree of design and implementation flexibility for dynamic collections has been found to be highly desirable in practice. Diverse dynamic collection data structures each have their advantages and disadvantages, and each such data structure typically also has diverse implementations, none of which is optimal for all cases. Therefore, it has not been possible thus far to devise a practical (i.e., comprehensible input code, efficient output code, and reasonable translator complexity) general-purpose programming language that provides for dynamic collection types in general. Instead, as in languages like LISP, one (or at most a few) dynamic collection types are typically provided by the language (e.g., lists for LISP). For problems that map easily to language-provided dynamic collection types, such languages can be very effective. However, for problems that don't map easily to the language-provided dynamic collection types, such languages tend to perform poorly.
Therefore, present-day handling of dynamic collections is typically performed according to one of the following two approaches: 1) A general approach (e.g., interfaces in object-oriented programming), which provides the variety and flexibility needed in practice, but incurs the disadvantage of complicated interface coding; and 2) A specialized approach (e.g., LISP, Haskell, etc.), which provides simplified type-based handling of some kinds of dynamic collections, but can have reduced performance for important practical applications.
Accordingly, it would be an advance in the art to provide a general approach for handling dynamic collections that is substantially simpler than the above-described manual coding of interfaces, without substantially reducing performance.